1. Field of the Invention
The present invention relates to a technique to obtain a passing order of a plurality of points, and more particularly to a beam direct-writing apparatus for performing beam direct-writing on a plurality of writing points on a substrate by using an electron beam and a light beam and an imaging apparatus for acquiring images on a plurality of imaging positions on a substrate.
2. Description of the Background Art
In an beam direct-writing apparatus for writing a circuit pattern on a semiconductor substrate (hereinafter, referred to as xe2x80x9csubstratexe2x80x9d) or an imaging apparatus for performing image pickup for inspection of a pattern and the like written on a substrate, a number of writing points or imaging positions (hereinafter, referred to generally as xe2x80x9ctarget pointsxe2x80x9d) on the substrate are accessed. For example, in the beam direct-writing apparatus, by irradiating a number of target points on the substrate with an electron beam, a number of points (microscopic patterns) are written on the substrate. In this case, the time required for the writing increases almost proportionally to the distance of a path passing through the target points.
Conventionally, in most cases, the path passing through all the target points is set according to the input order of data of the target points or the ascending or descending order of X coordinate and Y coordinate of the target points by defining the X coordinate axis and the Y coordinate axis (so-called xe2x80x9cXY sortxe2x80x9d) in advance.
Though the path can be quickly set by using a computer or the like according to the XY sort whose algorithm is simple, however, if the target points are scattered in a wide range, the obtained path disadvantageously becomes very long.
Though many methods of obtaining a path as short as possible with a complicate computational algorithm have been studied, these methods, for actual use, need the computation time which becomes exponentially longer as the number of target points increases and an expensive arithmetic circuit.
Such a method as disclosed in Japanese Patent Application Laid Open Gazette No. 2001-195112 is proposed, where the size of one divided region is determined in advance through a plurality of simulations of equally dividing a region containing target points and a path is set for each divided region by using a complicate algorithm. In this method, however, the time for the simulations is needed and when the target points are locally concentrated, the whole region is divided into unnecessarily small regions on the basis of the region where the target points are concentrated and this makes it impossible to obtain a preferable path.
It is an object of the present invention to easily obtain a preferable path.
The present invention is intended for a beam direct-writing apparatus for performing beam direct-writing on a substrate.
According to an aspect of the present invention, the beam direct-writing apparatus comprises a beam emission part for emitting a direct-writing beam onto the substrate, a deflection part for deflecting the beam, a holding part for holding the substrate, and a path setting part for obtaining a path passing through a plurality of writing points on the substrate, and in the beam direct-writing apparatus, the path setting part executes a region dividing step for dividing a two-dimensional writing region into a plurality of divided regions so that a divided region is smaller as density of writing points contained in said divided region is higher, a region passing order setting step for setting a region passing order which is an order for the path to pass through the plurality of divided regions, a writing point setting step for setting a first writing point and a second writing point for each of the plurality of divided regions on the basis of the region passing order, a sectional path setting step for obtaining a sectional path passing through points from the first writing point to the second writing point in each of the plurality of divided regions by using a predetermined path setting algorithm, and a sectional path connecting step for connecting the second writing point in each of the plurality of divided regions to the first writing point in the next divided region according to the region passing order.
The beam direct-writing apparatus makes it possible to easily obtain a preferable path passing through a plurality of writing points.
Preferably, the region dividing step comprises a simple division step for dividing the writing region into a predetermined number of divided regions which have almost the same size, and a recursive execution step for recursively executing the simple division step for one out of the predetermined number of divided regions which is selected on the basis of density of the plurality of writing points, and further preferably, a region passing order among divided regions which are obtained in the first execution of the simple division step is determined in advance, region passing orders among divided regions which are obtained in the second and subsequent executions of the simple division step are determined in advance on the basis of passing manners of a divided region before division, and the region dividing step and the region passing order setting step are executed substantially at the same time.
This makes it possible to obtain a path for a short time.
According to a preferred embodiment, the region passing orders among the divided regions which are obtained in the second and subsequent executions of the simple division step are determined in advance by using a fractal curve generation algorithm.
The present invention allows the starting point and the terminal point of a path to be close to each other by making the region passing order among the divided regions obtained in the first execution of the simple division step in a loop.
The present invention is also intended for a technique to obtain a path passing through a plurality of imaging positions in an imaging apparatus for performing image pickup of a substrate, and further intended for a computer-readable medium carrying a program which causes a computer to obtain a preferable path passing through a plurality of points, and a method of obtaining a preferable path in a various technical fields.
These and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.